This invention relates to a graphic layout compaction system and a graphic layout compaction method.
An automatic layout system is utilized for designing a layout of a large-scale semiconductor integrated circuit or a layout of a printed-circuit board. The large-scale semiconductor integrated circuit comprises a lot of semiconductor cells while the printed-circuit board mounts a lot of parts thereon. The semiconductor cells may be merely referred to cells. The semiconductor cells and the parts are collectively called components in the present specification. Although each component has at least one terminal (which is called a component terminal), the component terminal may be called the component. In addition, in the automatic layout system of the type, various compaction techniques for moving components with the components linked are already proposed.
By way of example, a conventional graphic compaction system is described in Japanese Unexamined Patent Publication of Tokkai No. Hei 9-204,461 or JP-A 9-204,461 (which will be herein called a first prior art) which is published on Aug. 5, 1997 and which has a title of invention as "COMPACTION DEVICE." The graphic compaction system according to JP-A 9-204,461 compacts components with relative position relationship of the components held. However, this graphic compaction system is disadvantageous in that it is impossible to compact a pattern having routes or wires between component terminals. This is because this graphic compaction system places or arranges only the parts (the components) on a printed-circuit board in a stage prior to routing or wiring between terminals (the component terminals) of the parts and then compacts its placement or arrangement.
In the manner as described above, a technique using a constraint graph is frequently utilized in a conventional compaction processing for compacting the routes or wires together with semiconductor cells or parts (the components). As a compaction technique using the constraint graph, a jog insertion compaction technique is proposed which modifies structure of the constraints graph by inserting a bent part called "jog" in the routing or wiring thereby enable to reduce an area of the layout and to correct places with design-rule violations (see reference (1): Wataru Yamamoto, Toru Awashima, Masao Sato, and Tatsuo Ohtsuki, "A Chip Compaction Method on Constraint Graph and the Experimental Result", TECHNICAL REPORT OF IEICE, VLD91-93, pp. 41-48, 1991, reference (2): Wataru Yamamoto, Toru Awashima, Masao Sato, and Tatsuo Ohtsuki, "A Chip Spacing Method for Layouts with Design-Rule Violations", TECHNICAL REPORT OF IEICE, VLD91-120, pp. 37-44, Feb. 7, 1991, and reference (3): Wataru Yamamoto, Toru Awashima, Masao Sato, and Tatsuo Ohtsuki, "A Chip Spacer with Automatic 45.degree. Diagonal Wiring Generation", TECHNICAL REPORT OF IEICE, VLD91-123, pp. 17-24, 1992).
In the manner which will later be described in conjunction with FIG. 1, a conventional layout compaction device comprises a cell placement processing unit (cell arrangement processing unit), an inter-cell routing processing unit (inter-cell wiring processing unit), a longest rout searching unit, a layout enlarging unit, a layout correction designating unit, a layout automatic compressing unit (compaction unit), a layout data memory, and a layout result display unit.
The conventional layout compaction device having such structure operates in the manner which will presently be described.
The cell placement processing unit carries out processing of placement or arrangement for cells in the manner as is well known in the art and stores cell layout data indicative of a layout of the cells in the layout data memory. The inter-cell routing processing unit carries out processing of routing or wiring between the cells in the manner as is well known in the art and stores routing layout data (wiring layout data) indicative of a layout of the routing or the wiring in the layout data memory. The longest route searching unit searches a series of graphic elements having the longest route in the layout stored in the layout data memory in order to compact a layout of each cell and the routing or wiring on an LSI chip into a smaller area and displays it in the layout result display section. The layout enlarging unit inserts a space crossing the longest route of its constraint graph in the layout in the manner which will later be described. The layout correction designating unit responds to a commend from an operator and moves a part from the longest route of the constraint graph so as to shorten the longest route in the manner which will later be described. In addition, the compaction unit (the automatic layout compressing unit) compacts the layout indicative of a corrected result in the manner which will later be described.
However, in a case of carrying out compaction of the layout so as to reduce the layout in both longitudinal and lateral directions, the conventional compaction unit reduces the layout in two steps so as to first reduce it in one direction (e.g. the longitudinal direction) and to subsequently reduce it in another direction (e.g. the lateral direction). Therefore, when the layout is first reduced in the longitudinal direction, the parts or the components crowd in the longitudinal direction and it results in preventing reduction of placement or arrangement on subsequently reducing placement or arrangement of the parts or the components and the layout of the routing or the wiring in the lateral direction.
In addition, those skilled in the art may hit upon a method comprising the steps of extending the Dijkatra method, of simultaneously evaluating a movable distance of the longitudinal direction and another movable distance of the lateral direction for each part or component, and of moving the parts or the components in order ascending the movable distances in its direction to place or arrange the parts or the components. However, this method is disadvantageous in that placement or arrangement of the parts or the components crowed in a particular direction selected from the longitudinal direction and the lateral direction prevents the parts or the components from subsequently moving in a direction perpendicular to the particular direction.
The reason for this defect is as follows. This conventional compaction system carries out compaction of the layout so as to first move all of the parts or the components in the longitudinal direction with all of the parts or the components pushed to touch a substrate end and to subsequently move all of the parts or the components in the lateral direction with all of the parts or the components pushed to touch the substrate end. Therefore, an initial result of placement or arrangement for semiconductor cells or parts is not reflected to the layout after compaction and compaction in an initial direction results in unbalancing placement or arrangement of the parts or the components. As a result, compaction of the semiconductor cells and the parts in the next direction is prevented.
In addition, to improve this defect, still another conventional graphic compaction system is described in Japanese Unexamined Patent Publication of Tokkai No. Sho 63-181,349 or JP-A 63-181,349 (which will be herein called a third prior art) which is published on Jul. 26, 1988 and which has a title of invention of "LAYOUT DESIGN EQUIPMENT FOR LSI." The graphic compaction system according to JP-A 63-181,349 moves semiconductor cells in a symmetrical direction towards a center of the layout for a chip before routing or wiring process for an LSI, compacts the layout so that the semiconductor cells collect in a center direction of the chip, and makes routing or wiring between the semiconductor cells.
However, the third prior art has a defect as follows. That is, the third prior art divides an area of the layout about the center of the chip into four divided areas and carries out compaction in the respective divided areas. In addition, in each divided area, the third prior art first carries out primary compaction of the semiconductor cells in a first direction and subsequently carries out secondary compaction of the semiconductor cells in a second direction perpendicular to the first direction. As a result, a result of the primary compaction may prevent the semiconductor cells from moving in the second direction in the secondary compaction.
The reason for this defect is as follows. That is, the conventional compaction system carries out compaction of the layout so as to move the layout in a predetermined designated direction in spite of moving the semiconductor cells (the parts) either in the longitudinal direction or in the lateral direction. As a result, when a difficulty occurs in the designated direction for moving the parts or the components, movement of the parts or the components is prevented.
In addition, to improve this defect, yet another conventional graphic compaction system is described in Japanese Unexamined Patent Publication of Tokkai No. Bei 5-274,392 or JP-A 5-274,392 (which will be herein called a fourth prior art) which is published on Oct. 22, 1993 and which has a title of invention of "LAYOUT COMPACTION SYSTEM." The graphic compaction system according to JP-A 5-274,392 comprises a pattern division section for dividing a substrate into a plurality of partial areas each having routing or wiring as a boundary and a plurality of partial pattern compression sections for the respective partial areas. The partial pattern compression sections compress the shape of the partial areas in the substrate to the left or right from a left-hand end of the substrate and compress the shape of the partial areas in the substrate to up and down from an upper end of the substrate. Therefore, the graphic compaction system according to JP-A 5-274,392 uniformly compacts the entire area of the substrate with relationship up and down and left and right in the area maintained.
However, the fourth prior art has a defect as follows. That is, although the fourth prior art can compress the partial areas of the substrate by using partial compaction, it is impossible to deal with oblique routing or wiring. This is because the fourth prior art carries out expansion and contraction of the partial areas by expanding and contracting the routing or the wiring in the longitudinal and lateral directions on the premise that the routing or wiring is crosswise routing or wiring.
In addition, a method based on the Bounded Sliceline-Grid (BSG) is proposed which comprises the steps of designating a rectangular area enclosing parts by the BSG and of concurrently compacting the area in the longitudinal and lateral directions by changing a size of the area. (see reference (4): Keishi Sakanushi, Tsuyoshi Kurasawa, Yasuhiro Takashima, Shigetoshi Nakatake, and Yoji Kajitani, "Concurrent Representation and Optimization of Placement and Route on BSG", TECHNICAL REPORT OF IEICE, VLD97-40, pp. 175-182, June 1991). However, this method has defects as follows. A first defect is that it is impossible to move both of circular parts mutually when the circular parts are in contact with each other in an oblique direction. A second defect is that it is impossible to compact the layout having the oblique routing or wiring.